from typing import List


class Solution(object):
    # DFS 回溯 + 剪枝
    def combinationSum(self, candidates, target) -> List[List[int]]:
        res = []

        # 搜索时一般会产生重复的现象
        # 按照某一顺序搜索，已经是剪枝了
        # 情况一：跳过当前位置
        # 情况二：加入当前位置，若仍然小，继续当前位置搜索
        # 因为两种情况分支会形成一个二叉树，会更加深，更加占用栈空间
        def helper(i, sofar):
            if i >= len(candidates): return
            helper(i+1, sofar[:])  # 每次 DFS 都创建了新的状态变量，比较耗空间和时间
            sofar.append(candidates[i])
            if sum(sofar) == target:
                res.append(sofar)
            elif sum(sofar) < target:
                helper(i, sofar[:])
        
        helper(0, [])
        return res
    
    # DFS 的时候按照某种顺序搜索，可以做到在搜索的时候去重。
    # 多叉树写法，貌似栈空间使用更少
    # 减去每个元素 -> 都是一个分支；但是会出现重复的情况
    # DFS 剪枝提速：排序
    def combinationSumFaster(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        n = len(candidates)
        candidates.sort()  # 按从小到大的顺序搜索，方便进行剪枝

        # 这里因为可以重复获取，所以不需要用 used, 而记录开始考虑的 begin 值
        def dfs(path, begin, target):  # target is residue
            if target == 0:
                res.append(path[:])
                return
            for i in range(begin, n):
                if target - candidates[i] < 0:
                    break  # 直接退出循环，因为后面的只会更大
                path.append(candidates[i])
                dfs(path, i, target-candidates[i])
                path.pop()

        dfs(path=[], begin=0, target=target)
        return res


if __name__ == "__main__":
    soln = Solution()
    print(soln.combinationSum([3,5,8], 9))
    print(soln.combinationSum([3,5,8], 11))
    print(soln.combinationSum([2,7], 7))
    print(soln.combinationSum([2,7,6,3,5,1], 9))
